package com.ai.zuochengyun.phase01.class02;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Code04_OneKTimesTheOtherMTimes {
    public static void main(String[] args) {
        // 有几种数
        int kinds = 4;
        int range = 200;
        int testTimes = 100000;
        int max = 9;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            // 获取1~9范围内的值
            int a = (int)(Math.random() * max) + 1;
            int b = (int)(Math.random() * max) + 1;

            // 将a、b中较小值作为k，较大值作为m，如果a、b相等，那么就将m++
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            if (k == m) {
               m++;
            }

            int[] arr = randomArray(kinds, range, k, m);
            int num1 = onlyKTimes(arr, k, m);
            int num2 = test(arr, k, m);
            if (num1 != num2) {
                System.out.println("出现错误!"+"k="+k+",m="+m);
                for (int n : arr) {
                    System.out.print(n+ " ");
                }
                return;
            }
        }
        System.out.println("测试结束");

    }

    private static int[] randomArray(int kinds, int range, int k, int m) {
        // 只有一个数出现了k次，其他数都出现了m次
        int size = k +(kinds - 1)*m;
        int[] arr = new int[size];

        Set<Integer> existsNum = new HashSet<>();
        // 填充出现了k次的数
        int index = 0;
        // 切记，生成的value值也需要加入set集合中
        int value = randomNumber(range);
        existsNum.add(value);
        for (; index < k; index++) {
            arr[index] = value;
        }

        // 填充出现了m次的数
        for (int i = 1; i < kinds; i++) {
            // 生成当前种类要插入的数
            do {
                value = randomNumber(range);
            } while (existsNum.contains(value));
            existsNum.add(value);

            // 该数出现了多少次
            for (int j = 0; j < m; j++) {
                arr[index] = value;
                index++;
            }
        }

        // 最终将数组进行乱序排列
        for (int i = 0; i < arr.length; i++) {
            int idx = (int)(Math.random() * arr.length);
            int temp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = temp;
        }

        return arr;
    }

    private static int randomNumber(int range) {
        return (int)(Math.random() * range) + 1;
    }

    /**
     * 请保证arr中，只有一个数出现了k次，其他数都出现了m次
     * 求出现了k次的数，M>1 K<M
     * @param arr
     * @param k 出现了k次
     * @param m 出现了m次
     * @return
     */
    private static int onlyKTimes(int[] arr, int k, int m) {
        // int长度为32位，所以声明一个32位的长度来存储词频数据
        int bits = 32;
        int[] t = new int[bits];

        // 词频统计，将每个位置的1的个数进行累加
        // t[0] 表示0位置的1出现的次数
        // t[i] 表示i位置的1出现的次数
        for (int num : arr) {
            // 固定循环32次，所以即便两个for循环嵌套，时间复杂度还是O(N)
            for (int i = 0; i < bits; i++) {
                // num在i位置上为1
                // & 只有当2个二进制都为1时，结果才为1，其他均为0
                // 假设num为00110110
                // num >> 0,还是自己
                // num >> 3,00000110  和1 00000001 与，得到0，那么就表第4位上没有1
                // 把右侧的移除掉，获取每一位上是否有1存在
                if (((num >> i) & 1) != 0) {
                    t[i]++;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < bits; i++) {
            int num = t[i];
            // 有余数，表示没能被m整除
            if (num % m != 0) {
                // 1向左移动i位
                // 或运算不会改变其他位上的值，只会改变当前位的值
                // 某个位置上有1，就或进去
                ans |= (1 << i);
            }
        }
        return ans;
    }


    private static int test(int[] arr, int k, int m) {
        // 统计词频
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == k) {
                return entry.getKey();
            }
        }
        return -1;
    }
}
